package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;


public class LeetCode_day3 {
	
	/**
	 * Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). 
	 * n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). 
	 * Find two lines, which together with x-axis forms a container, 
	 * such that the container contains the most water. You may not slant the container.
	 * @param as
	 * @return
	 */
	public static int[] containerWithMostWater(int[] as){
		//check valid input
		if(as == null || as.length < 2) return null;
		for(int i = 0 ; i < as.length ; i++) if(as[i] <= 0) return null;
		//begin procedure
		int[] lines = new int[2]; lines[0] = as[0]; lines[1] = as[1];
		int maxArea = Math.min(as[0], as[1]);
		
		//the longest width would be as.length - 1
		for(int width = 1 ; width < as.length-1 ; width++){
			//find the new maxArea
			double minHight = maxArea /(double)width;
			for(int l = 0 ; l < as.length - width ; l++){//for every possible left//be careful about as.length-width
				if(as[l] <= minHight) continue;
				int r = l + width;//find the corresponding r
				if(as[r] <= minHight) continue;
				maxArea = Math.min(as[l], as[r]) * width;
				lines[0] = as[l]; lines[1] = as[r];
			}
		}
		return lines;
	}
	
	
	/**
	 * ! Given an integer, convert it to a roman numeral.
	 * Input is guaranteed to be within the range from 1 to 3999.
	 * Left is minus, right is plus
	 * Left minus digit == 1
	 * Right plus digit <= 3
	 * @param d
	 * @return
	 */
	public static String integerToRoman(int d){
		//check boundary condition
		if(d < 1 || d > 3999) return null;
		//procedure
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50);
		map.put('C', 100); map.put('D', 500); map.put('M', 1000);
		return null;
	}
	
	/**
	 * Given a roman numeral, convert it to an integer.
	 * Loop from right to left
	 * If next digit is larger or equal to current digit, add next digit;
	 * If next digit is smaller to current digit, minus next digit;
	 * @param str
	 * @return
	 */
	public static int romanToInteger(String str){
		//check boundary
		if(str == null || str.isEmpty()) return 0;
		if(!str.matches("[I,V,X,L,C,D,M]*")) return 0;
		
		char[] s = str.toCharArray();
		int result = 0;
		//procedure
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50);
		map.put('C', 100); map.put('D', 500); map.put('M', 1000);
		
		char pre = s[s.length - 1]; result = map.get(s[s.length-1]);
		for(int i = s.length - 2 ; i >= 0 ; i--){
			if(map.get(s[i]) >= map.get(pre)) {//when s[i] >= pre, this means plus
				result = map.get(s[i]) + result;
			}else{//minus
				result -= map.get(s[i]);
			}
			pre = s[i];
		}
		return result;
	}
	
	/**
	 * ! Write a function to find the longest common prefix string amongst an array of strings.
	 * Declaration of the problem:
	 * 	  -a prefix shared by at least two strings in the array is called common prefix
	 * @param list
	 * @return
	 */
	public static String longestCommonPrefix(String[] list){
		//check boundary
		if(list == null || list.length < 1) return null;
		for(int i = 0 ; i < list.length ; i++) list[i] = list[i].toLowerCase();
		
		int maxLen = 0;
		TrieTreeNode nd = null;
		
		//build trie tree
		ArrayList<TrieTreeNode> tree = new ArrayList<TrieTreeNode>();
		TrieTreeNode root = new TrieTreeNode();
		root.depth = 0;
		root.children = new TrieTreeNode[27];
		//insert all strings into the trie tree
		for(int i = 0 ; i < list.length ; i++){
			char[] s = list[i].toCharArray();
			TrieTreeNode curNode = root;
			for(int j = 0 ; j < s.length ; j++){
				int ind = s[j]-'a';
				if(curNode.children == null) curNode.children = new TrieTreeNode[27];
				
				if(curNode.children[ind] != null) curNode = curNode.children[s[j]-'a'];
				else {
					//add child to curNode
					curNode.children[ind] = new TrieTreeNode();
					curNode.children[ind].depth = curNode.depth + 1;
					curNode.children[ind].par = curNode;
					curNode.children[ind].val = s[j];
					curNode.cNum++;
					
					//if it's the end of the string
					if(j == s.length - 1){
						curNode.children[ind].children = new TrieTreeNode[27];
						curNode.children[ind].children[26] = new TrieTreeNode();//tree need not add this child because it's a leaf
						//no need to define parent of this node
						curNode.children[ind].children[26].depth = curNode.children[ind].depth+1;
						curNode.cNum++;
					}
					tree.add(curNode.children[ind]);
					curNode = curNode.children[ind];
				}
			}
		}
		//find the most common prefix
		for(TrieTreeNode node : tree){
			if(node.cNum >= 2){
				if(node.depth > maxLen){
					maxLen = node.depth;
					nd = node;
				}
			}
		}
		if(maxLen == 0) return null; // no common prefix
		//get the prefix
		char[] prefix = new char[maxLen];
		int ind = maxLen-1;
		while(ind >= 0){
			prefix[ind] = nd.val;
			nd = nd.par;
			ind--;
		}
		
		return String.valueOf(prefix);
	}

	
	/**
	 * Given an array S of n integers, 
	 * are there elements a, b in S such that a + b = target? 
	 * Find all unique combinations.
	 * @param list
	 * @param target
	 * @return
	 */
	public static List<int[]> twoSum(int[] list, int target){
		//check boundary
		if(list == null || list.length < 2) return null;
		
		//main procedure
		Arrays.sort(list);
		List<int[]> res = new ArrayList<int[]>();
		//find middle numbers 
		//(equals to the target / 2 or two left or right numbers that are closest to target / 2)
		double half = target / 2.0;
		double flag = 0.0;
		for(int i = 0 ; i < list.length-1 ; i++){
			if(i-1 >= 0 && list[i] == list[i-1]) continue;
			if(list[i] == half) {
				flag = i;
				break;
			}
			if((list[i] - half) < 0 && (list[i+1] - half)> 0){
				flag = (i+i+1)*0.5;
				break;
			}
		}
		
		if(flag == 0.0) return null;//invalid input
		
		int r = list.length-1;
		for(int l = 0 ; l < half && r > l ; l++){//notice about r > l
			while(list[l] + list[r] > target){
				r--;
			}
			if(list[l] + list[r] == target)
				res.add(new int[]{list[l],list[r]});
			r--;//what if {1,2,3,3,4}, duplicates in list ???????
		}
		return res;
	}
	
	/**
	 * Optimize
	 * @param list
	 * @param target
	 * @return
	 */
	public static List<int[]> twoSum1(int[] list, int target){
		//check boundary
		if(list == null || list.length < 2) return null;
		//main procedure
		Arrays.sort(list);
		List<int[]> res = new ArrayList<int[]>();
		
		int l = 0 , r = list.length-1;
		while(l < r){
			int sum = list[l] + list[r];
			if(sum < target) l++;
			else if(sum > target) r--;
			else{
				res.add(new int[]{list[l], list[r]});
				l++;
			}
		}
		return res;
	}
	
	/**
	 * Given an array S of n integers, 
	 * are there elements a, b, c in S such that a + b + c = target? 
	 * Find all unique triplets in the array which gives the sum of zero.
	 * 
	 * Note:
	 * Elements in a triplet (a,b,c) must be in non-descending order. (ie, a <= b <= c)
	 * The solution set must not contain duplicate triplets.
	 * 
	 * Analysis:
	 * 1) pick a number a to be the smallest one in the triplet
	 * 2) then we should find an other two numbers b, c 
	 * 			such that b + c = target - a && a < b < c
	 * 3) knowing list[i] = a, we know that list[i] + list[i+1] + list[i+2] <= target
	 * 4) then we have the limiting condition list[i] <= target - list[i+1] - list[i+2]
	 * 5) then the question is reduced to twoSum problem.
	 * 
	 * see http://lostincompilation.blogspot.com/2013/07/find-quadruplets-hard.html
	 * @param list
	 * @return
	 */
	public static List<int[]> threeSum(int[] list, int target){
		//check boundary
		if(list == null || list.length < 3) return null;
		
		//main procedure
		Arrays.sort(list);
		List<int[]> res = new ArrayList<int[]>();
		for(int i = 0 ; i < list.length-2 && list[i] <= (target-list[i+1]-list[i+2]) ; i++){
			if(i-1 >= 0 && list[i] == list[i-1]) continue;//remove duplicates, notice, cannot do like i and i+1
			//find other two numbers
			int ntarget = target - list[i];
			
			int l = i+1, r = list.length-1;
			while(l < r){
				int sum = list[l] + list[r];
				if(sum == ntarget) {
					res.add(new int[]{list[i], list[l], list[r]});
					l++;
				}else if(sum > ntarget) r--;
				else l++;
			}	
		}
		return res;
	}
	
	
	public static List<String> letterCombinationOfPhoneNumber(String digits){
		//check boundary condition
		if(digits == null || digits.isEmpty()) return null;
		//main procedure
		HashMap<Integer, char[]> map = new HashMap<Integer, char[]>();
		map.put(0, null);map.put(1, null);
		map.put(2, new char[]{'a','b','c'}); map.put(3, new char[]{'d','e','f'});
		map.put(4, new char[]{'h','g','i'}); map.put(5, new char[]{'j','k','l'});
		map.put(6, new char[]{'m','n','o'}); map.put(7, new char[]{'p','q','r','s'});
		map.put(8, new char[]{'t','u','v'}); map.put(9, new char[]{'w','x','y','z'});
		
		char[] d = digits.toCharArray();
		List<String> pre = new ArrayList<String>();
		for(char c : map.get(Character.getNumericValue(d[0]))){
				String sb = String.valueOf(c);
				pre.add(sb);
		}
		
		for(int i = 1 ; i < d.length ; i++){
			List<String> cur = new ArrayList<String>();
			for(String sb : pre)
				for(char c : map.get(Character.getNumericValue(d[i])))
					cur.add(new String(sb+c));
			pre = cur;
		}
		return pre;
	}

	
	/**
	 * Given a string containing just the characters 
	 * '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
	 * @param str
	 * @return
	 */
	public static boolean validParentheses(String str){
		//check boundary condition
		if(str == null || str.isEmpty()) return false;
		//main procedure
		LinkedList<Character> stack = new LinkedList<Character>();
		char[] s = str.toCharArray();
		
		for(char c : s){
			if(c == '(' || c == '{' || c == '[') stack.push(c);
			else if(c == ')' || c == '}' || c == ']'){
				if(stack.isEmpty()) return false;
				char top = stack.pop();
				if(c == ')' && top == '(') continue;
				if(c == ']' && top == '[') continue;
				if(c == '}' && top == '{') continue;
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		//int[] lines = containerWithMostWater(new int[]{1,2,3,4});
		//System.out.println(lines[0] + " " + lines[1]);
		//System.out.println(romanToInteger("MD"));
		//char[] c = new char[2];
		//System.out.println(c[0] == '\0');
		String[] list = new String[]{"abc","abcs","ac"};
		System.out.println(longestCommonPrefix(list));
		List<int[]> list2 = threeSum(new int[]{-1, 0, 1, 2, -1, -4}, 0);
		List<String> list3 = letterCombinationOfPhoneNumber("342");
		System.out.println(validParentheses("()[]{}as{dne(sal)ads}sds"));
		System.out.println();
	}
}

class TrieTreeNode{
	public TrieTreeNode[] children = null;
	public char val;
	public int depth;
	public int cNum = 0;
	public TrieTreeNode par = null;
}

/**
 * Notice:
 * 'a' - 'a' = 0
 * 'b' - 'b' = 1
 * 'B' - 'a' = -31
 * 
 * char[] c = new char[2];
 * System.out.println(c[0] == '\0'); is true
 * 
 * How to get unique values from array:
 * String[] unique = new HashSet<String>(Arrays.asList(array)).toArray();
 * 
 * convert char to integer:
 * 	Integer.valueOf(c) is wrong
 * 	Character.getNumericValue(c) is correct
 * */
